// Tags:
#include <algorithm>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <queue>

typedef long long ll;

template <typename T>
inline T &read(T &x) {
  x = 0;
  bool f = false;
  short ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f = true;
    ch = getchar();
  }
  while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ '0'), ch = getchar();
  if (f) x = -x;
  return x;
}

const int N = 2e2 + 25;
int n, m, q, cnt, dep[N], fa[N], top[N], siz[N], son[N], f[N];
int e_cnt = 1, heads[N];
bool ontree[N << 1];
ll dis[45][N];

struct Node {
  ll d;
  int id;
  Node(ll d, int id) : d(d), id(id) {}
  inline bool operator<(const Node &rhs) const { return d > rhs.d; }
};

std::priority_queue<Node> pq;

struct Edge {
  int nxt, v, w, id;
  Edge() {}
  Edge(int u, int v, int w, int id) : nxt(u), v(v), w(w), id(id) {}
  inline bool operator<(const Edge &rhs) const { return w < rhs.w; }
} e[N << 1], g[N];

inline void add(int u, int v, int w) {
  e[++e_cnt].v = v, e[e_cnt].nxt = heads[u], heads[u] = e_cnt, e[e_cnt].w = w;
}

int find(int x) { return f[x] == x ? x : f[x] = find(f[x]); }

void dfs1(int u) {
  siz[u] = 1;
  for (int i = heads[u], v; i; i = e[i].nxt) {
    if (ontree[i] && (v = e[i].v) != fa[u]) {
      dep[v] = dep[u] + 1, fa[v] = u, dis[0][v] = dis[0][u] + e[i].w;
      dfs1(v);
      siz[u] += siz[v];
      if (siz[son[u]] < siz[v]) son[u] = v;
    }
  }
}

void dfs2(int u) {
  if (son[u]) top[son[u]] = top[u], dfs2(son[u]);
  for (int i = heads[u], v; i; i = e[i].nxt) {
    if (ontree[i] && (v = e[i].v) != fa[u] && v != son[u]) {
      top[v] = v;
      dfs2(v);
    }
  }
}

inline void dij(int s, ll dis[N]) {
  memset(dis, 0x3f, sizeof(ll) * N);
  pq.push(Node(dis[s] = 0, s));
  while (!pq.empty()) {
    int u = pq.top().id, d = pq.top().d;
    pq.pop();
    if (d != dis[u]) continue;
    for (int i = heads[u], v; i; i = e[i].nxt) {
      if (dis[v = e[i].v] > dis[u] + e[i].w) {
        dis[v] = dis[u] + e[i].w;
        pq.push(Node(dis[v], v));
      }
    }
  }
}

inline int getlca(int u, int v) {
  while (top[u] != top[v])
    dep[top[u]] > dep[top[v]] ? u = fa[top[u]] : v = fa[top[v]];
  return dep[u] > dep[v] ? v : u;
}

int main() {
#ifndef ONLINE_JUDGE
#ifdef LOCAL
  freopen64("/tmp/CodeTmp/testdata.in", "r", stdin);
  freopen64("/tmp/CodeTmp/testdata.out", "w", stdout);
#else
  freopen("graph.in", "r", stdin);
  freopen("graph.out", "w", stdout);
#endif
#endif

  read(n), read(m);
  for (int i = 1, u, v, w; i <= m; ++i) {
    read(u), read(v), read(w);
    add(u, v, w), add(v, u, w);
    g[i] = Edge(u, v, w, i);
  }
  for (int i = 1; i <= n; ++i) f[i] = i;
  std::sort(g + 1, g + m + 1);
  for (int i = 1; i <= m; ++i) {
    if (find(g[i].nxt) != find(g[i].v)) {
      f[find(g[i].nxt)] = find(g[i].v);
      ontree[g[i].id << 1] = ontree[(g[i].id << 1) | 1] = true;
    }
  }
  read(q);
  dep[1] = 1, fa[1] = 1, top[1] = 1, dfs1(1), dfs2(1);
  for (int i = 2; i <= e_cnt; i += 2) {
    if (!ontree[i]) {
      dij(e[i].v, dis[++cnt]);
      dij(e[i ^ 1].v, dis[++cnt]);
    }
  }
  for (int u, v; q; --q) {
    read(u), read(v);
    ll ans = dis[0][u] + dis[0][v] - (dis[0][getlca(u, v)] << 1);
    for (int i = 1; i <= cnt; ++i) {
      ans = std::min(ans, dis[i][u] + dis[i][v]);
    }
    printf("%lld\n", ans);
  }
  return 0;
}